Valid word square

Time: O(MxN); Space: O(1); easy

Given a sequence of words, check whether it forms a valid word square.

A sequence of words forms a valid word square if the k^th row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

The number of words given is at least 1 and does not exceed 500. Word length will be at least 1 and does not exceed 500. Each word contains only lowercase English alphabet a-z. Have you met this question in a real interview?

Example 1

Input: words =

[
  "abcd",
  "bnrt",
  "crmy",
  "dtye"
]

Output: True

Explanation:

  • The first row and first column both read “abcd”,

  • The second row and second column both read “bnrt”,

  • The third row and third column both read “crmy”,

  • The fourth row and fourth column both read “dtye”,

  • Therefore, it is a valid word square.

Example 2:

Input: words =

[
  "abcd",
  "bnrt",
  "crm",
  "dt"
]

Output: True

Explanation:

  • The first row and first column both read “abcd”,

  • The second row and second column both read “bnrt”,

  • The third row and third column both read “crm”,

  • The fourth row and fourth column both read “dt”,

  • Therefore, it is a valid word square.

Example 3:

Input: words =

[
  "ball",
  "area",
  "read",
  "lady"
]

Output: False

Explanation:

  • The third row reads “read”,

  • Therefore, it is NOT a valid word square.

[1]:

class Solution1(object):
    def validWordSquare(self, words):
        """
        :type words: List[str]
        :rtype: bool
        """
        for i in range(len(words)):
            for j in range(len(words[i])):
                if j >= len(words) or i >= len(words[j]) or \
                   words[j][i] != words[i][j]:
                   return False
        return True

[2]:

s = Solution1()
words = [
      "abcd",
      "bnrt",
      "crmy",
      "dtye"
    ]
assert s.validWordSquare(words) == True
words = [
      "abcd",
      "bnrt",
      "crm",
      "dt"
    ]
assert s.validWordSquare(words) == True
words =  [
      "ball",
      "area",
      "read",
      "lady"
    ]
assert s.validWordSquare(words) == False